package basic.courseLearn16.problem;

import org.junit.Test;

//给定行数和列数，一个人在表格中（a，b），走向任一方向随机，不能出现越界情况，问走k步之后最后在范围内走法统计
public class ChessboardLimit {

    @Test
    public void test_solution_1() {
        int row = 10;
        int col = 10;
        int x = 1;
        int y = 9;
        int k = 3;
        int count = solution_1(row, col, x, y, k);
        System.out.println(count);
    }

    @Test
    public void test_solution_2() {
        int row = 4;
        int col = 4;
        int x = 2;
        int y = 1;
        int k = 1;
        int[][][] memo = new int[row+1][col+1][k+1];
        //初始化记忆表
        for (int i = 0; i <= row; i++) {
            for (int j = 0; j <= col; j++) {
                for (int l = 0; l <= k; l++) {
                    memo[i][j][l] = -1;
                }
            }
        }
        System.out.println(solution_2(memo, row, col, x, y, k));
    }

    @Test
    public void test_solution_3() {
        int row = 4;
        int col = 4;
        int x = 4;
        int y = 1;
        int k = 3;
        int count = solution_3(row, col, x, y, k);
        System.out.println(count);
    }

    @Test
    public void check(){
        int count = 1_000; //测试次数
        int num_range = 4; //测试范围[1-10]
        for (int i = 0; i < count; i++) {
            int x = (int)(Math.random() * num_range)+1; //[0-10]
            int y = (int)(Math.random() * num_range)+1; //[0-10]
            int power = (int)(Math.random() * num_range)+1;
            int ways_1 = solution_1(num_range,num_range,x,y,power);
            int[][][] memo = new int[num_range+1][num_range+1][power+1];
            //初始化memo数组
            for (int k = 0; k < num_range+1; k++) {
                for (int j = 0; j < num_range+1; j++) {
                    for (int l = 0; l <= power; l++) {
                        memo[k][j][l] = -1;
                    }
                }
            }
            int ways_2 = solution_2(memo,num_range,num_range,x,y,power);
            int ways_3 = solution_3(num_range,num_range,x,y,power);
            if (ways_1!= ways_2 || ways_1!= ways_3){
                System.out.println("error");
                System.out.println("x="+x+",y="+y+",power="+power);
                System.out.println("ways_1="+ways_1+",ways_2="+ways_2+",ways_3="+ways_3);
                break;
            }
        }
        System.out.println("测试完成");


    }


    /**
     * 方法1:暴力递归
     * @param row 棋盘边界行数
     * @param col 棋盘边界列数
     * @param x 当前位置行(x>=1)
     * @param y 当前位置列(y>=1)
     * @param k 步数
     * @return
     */
    public int solution_1(int row,int col,int x,int y,int k){
        //1. 边界条件
        if (x > row || y > col || x < 1 || y < 1) {
            return 0;
        }
        //2. 递归终止条件
        if (k < 0) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        //3. 递归
        int count = 0;
        count += solution_1(row, col, x + 1, y, k - 1);
        count += solution_1(row, col, x - 1, y, k - 1);
        count += solution_1(row, col, x, y + 1, k - 1);
        count += solution_1(row, col, x, y - 1, k - 1);
        return count;
    }

    /**
     * 方法2:记忆表搜索
     * @param memo 记忆表
     * @param row 棋盘边界行数
     * @param col 棋盘边界列数
     * @param x 当前位置行(x>=1)
     * @param y 当前位置列(y>=1)
     * @param k 步数
     * @return
     */
    public int solution_2(int[][][] memo, int row,int col,int x,int y,int k){
        //1. 边界条件
        if (x > row || y > col || x < 1 || y < 1) {
            return 0;
        }
        //2. 递归终止条件
        if (k < 0) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        //3. 记忆表搜索
        if (memo[x][y][k] != -1) {
            return memo[x][y][k];
        }
        //4. 递归
        int count = 0;
        count += solution_2(memo,row, col, x + 1, y, k - 1);
        count += solution_2(memo,row, col, x - 1, y, k - 1);
        count += solution_2(memo,row, col, x, y + 1, k - 1);
        count += solution_2(memo,row, col, x, y - 1, k - 1);
        memo[x][y][k] = count;
        return count;
    }

    /**
     * 方法3:严格表结构
     * @param row 棋盘边界行数
     * @param col 棋盘边界列数
     * @param x 当前位置行(x>=1)
     * @param y 当前位置列(y>=1)
     * @param k 步数
     * @return
     */
    public int solution_3(int row,int col,int x,int y,int k){
        //1. 初始化严格表
        int[][][] memo = new int[row+1][col+1][k+1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                memo[i][j][0] = 1;
            }
        }
        //2. 递归计算
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= row; j++) {
                for (int l = 1; l <= col; l++) {
                    memo[j][l][i] =
                            ((j-1>=1)?memo[j-1][l][i-1]:0) +
                            ((j+1<=row)?memo[j+1][l][i-1]:0) +
                            ((l-1>=1)?memo[j][l-1][i-1]:0) +
                            ((l+1<=col)?memo[j][l+1][i-1]:0);
                }
            }
        }
        //3. 返回结果
        return memo[x][y][k];
    }





}
